package io.github.handyang.algorithms.sort;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.util.Arrays;

@Slf4j
public class MergeSortAlgorithms implements SortAlgorithms {

    @Override
    public void sort(int[] arr) {
        int[] helper = Arrays.copyOf(arr, arr.length);

//        mergeTL(arr, helper, 0, arr.length - 1);
        mergeBU(arr, helper);
    }

    /**
     * 自顶向下
     *
     * @param arr
     * @param start
     * @param end
     */
    protected void mergeTL(int[] arr, int[] helper, int start, int end) {
        if (start >= end) return;

        int len = end - start, mid = (len >> 1) + start;
        int start1 = start, end1 = mid;
        int start2 = mid + 1, end2 = end;

        mergeTL(arr, helper, start1, end1);
        mergeTL(arr, helper, start2, end2);

//        inPlaceMerge(arr, start1, start2, end2);
        merge(arr, helper, start1, start2, end2);
    }

    /**
     * 自底向上
     *
     * @param arr
     */
    protected void mergeBU(int[] arr, int[] helper) {
        for (int len = 1; len < arr.length; len += len) {
            for (int i = 0; i < arr.length - len; i += len + len) {
                merge(arr, helper, i, i + len, Math.min(i + len + len - 1, arr.length - 1));
            }
        }
    }

    @Test
    public void testMerge() {
        int[] arr = {10, 30, 50, 60, 80, 81, 20, 25, 55, 65, 73, 77};
        inPlaceMerge(arr, 0, 6, arr.length - 1);
        show(arr);
    }

    /**
     * 非原地归并
     *
     * {@code
     *  start     end
     *  +         +
     *  |         |
     * +v---------v+
     * |7|3|1|8|2|5|
     * +------^----+
     *        |
     *        +
     *        mid
     * }
     *
     * @param arr
     * @param start
     * @param mid
     * @param end
     */
    protected void merge(int[] arr, int[] helper, int start, int mid, int end) {
//        log.info("start:{}, mid:{}, end:{}", start, mid, end);
        for (int i = start; i <= end; i++) {
            helper[i] = arr[i];
        }

        int index = start;
        int i = start, j = mid;

        while (i < mid && j <= end) {
            arr[index++] = less(helper[i], helper[j]) ? helper[i++] : helper[j++];
        }

        while (i < mid) {
            arr[index++] = helper[i++];
        }
        while (j <= end) {
            arr[index++] = helper[j++];
        }
    }

    /**
     * 原地归并
     * <p>
     * https://blog.csdn.net/ACdreamers/article/details/24244643
     *
     * @param arr
     * @param start
     * @param mid
     * @param end
     */
    protected void inPlaceMerge(int[] arr, int start, int mid, int end) {
        int i = start, j = mid;

        while (i < j && j <= end) {
            while (i < end && less(arr[i], arr[j])) i++;

            int step = 0;

            while (j <= end && less(arr[j], arr[i])) {
                j++;
                step++;
            }

            exchangeRange(arr, i, j - step, j - 1);

            if (step == 0) i++;
            else i += step;
        }
    }

    /**
     * 交换相邻的两个数组区间
     *
     * @param arr
     * @param start
     * @param mid
     * @param end
     * @param <T>
     */
    protected void exchangeRange(int[] arr, int start, int mid, int end) {
        revertRange(arr, start, mid - 1);
        revertRange(arr, mid, end);
        revertRange(arr, start, end);
    }

    private void revertRange(int[] arr, int start, int end) {
        int i = start, j = end;

        while (i < j) {
            swap(arr, i++, j--);
        }
    }
}
